# -*- coding: utf-8 -*- 
# @project : 《Atcoder》
# @Author : created by bensonrachel on 2021/12/16
# @File : offer60.礼物的最大价值.py
class Solution(object):
    def getMaxValue(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        dp = [0] * (len(grid[0]) + 1)
        for ints in grid:
            for i in range(1, len(grid[0]) + 1):
                dp[i] = max(dp[i - 1] + ints[i - 1], dp[i] + ints[i - 1])
        return dp[-1]
